//============================================================================
// Name        : iotest.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

#define MAXPOINTS 5000

void read2()
{

	ifstream ii("/home/mudassir/code/data/1x2.txt");
	ofstream oo("/home/mudassir/code/data/1x3.txt");
	int year, age;
	double male;

	while(ii.good())
	{
		ii>>year>>age>>male>>male;
		//if(age>=20&&age<=40)
		{
			oo<<year<<", "<<age<<", "<<male<<", "<<endl;
		}
		ii>>male;
	}
	ii.close();
	oo.close();
}

void read3()
{

	ifstream ii("/home/mudassir/code/data/1x3.txt");
	ofstream oo("/home/mudassir/code/data/1x4.txt");
	int year, age;
	double male,temp;

	while(ii.good())
	{
		male=0;

		for(int i=0;i<21;i++)
		{
			ii>>year>>temp;
			male+=temp;
		}
		oo<<year<<"\t"<<male<<endl;
	}

	ii.close();
	oo.close();
}


void read4()
{
	ifstream ii("/home/mudassir/code/data/1x4.txt");
	ofstream oo("/home/mudassir/code/data/1x5.txt");
	int year, age;
	double male,temp;

	oo<<"z = matrix( c(";
	while(ii.good())
	{
		ii>>year>>temp;
		oo<<year<<","<<temp<<","<<endl;
	}

	ii.close();
	oo.close();

}

void readloud()
{
	ifstream i1("/home/mudassir/code/dbp.txt");
	ifstream i2("/home/mudassir/code/hdl.txt");
	ofstream oo("/home/mudassir/code/dh1.txt");
	int count=0;
	char str1[100],str2[100];
	while(count<60)
	{
		i1.getline(str1,80);
		i2.getline(str2,80);
		int tri = atoi(str1);
		int chol = atoi(str2);
		if(tri<=0 || chol<=0)
			continue;
		count++;
		oo<<tri<<","<<chol<<","<<endl;
	}
	i1.close();
	i2.close();
	oo.close();

}



class MyPoint
{
public:
	double x,y,angle;
	int operator ==(MyPoint two)
	{
		if(two.x==x &&two.y==y)
			return 1;
		return 0;
	}
	friend ostream& operator <<(ostream &os,const MyPoint &obj);
	friend bool operator<(const MyPoint &obj,const MyPoint &obj1);
};

ostream& operator <<(ostream &os,const MyPoint &obj)
{
      os<<"("<<obj.x<<", "<<obj.y<<")";
	//os<<obj.x<<endl<<obj.y;
      return os;
}


bool operator<(const MyPoint &obj,const MyPoint &obj1)
{
	return obj.angle<obj1.angle;
}


class MyLine
{
public:
	MyPoint a,b;
	friend ostream& operator <<(ostream &os,const MyPoint &obj);
};

ostream& operator <<(ostream &os,const MyLine &obj)
{
      os<<obj.a<<"---"<<obj.b;
      return os;
}


ifstream ii;
MyPoint P[MAXPOINTS];
int numberOfPoints;


int orient(MyLine l, MyPoint p)
{

    double position = ( (l.b.x-l.a.x)*(p.y-l.a.y) - (l.b.y-l.a.y)*(p.x-l.a.x) );
    return ( position > 0 );
}

int isinsidetriangle(MyPoint *list,MyPoint p)
{
    MyLine l1,l2,l3;
    l1.a=list[0];
    l1.b=list[1];

    l2.a=list[1];
    l2.b=list[2];

    l3.a=list[2];
    l3.b=list[0];

    cout<<l1<<endl<<l2<<endl<<l3<<endl;


    if(orient(l1,p)!=orient(l2,p)|| orient(l1,p)!=orient(l3,p) )
    return 0;

    return 1;
}

int isinsidetriangle(MyPoint a, MyPoint b,MyPoint c,MyPoint p)
{
	MyPoint list[3];
	list[0]=a;
	list[1]=b;
	list[2]=c;
	return isinsidetriangle(list,p);
}


int IsInsidePolygon(MyPoint *list, MyPoint pt, int sz)
{
    int start=0,mid=(sz-1)/2,last=sz-1;
    MyLine l;
    //MyPoint p;
    cout<<start<<", "<<mid<<", "<<last<<"\n";


    while( (last-start) > 2)
    {
        l.a = list[0];
        l.b = list[mid];

        if( orient(l,pt) == orient(l,list[start+1]) )
        {
            last=mid;
            mid = mid-(last-start)/2;
        }
        else
        {
            start=mid;
            mid = mid+(last-start)/2;
        }



        cout<<start<<", "<<mid<<", "<<last<<"\n";
    }


    //cout<<start<<", "<<mid<<", "<<last<<"\n";
    cout<<list[start]<<"\n";

    if(last-start==1)
    	return isinsidetriangle(list[0],list[start],list[start+1],pt);

    return (isinsidetriangle(list[0],list[start],list[start+1],pt)||
    		isinsidetriangle(list[0],list[start+1],list[start+2],pt) );
}

void PolygonIntersection()
{
/*
Obs1: vertices of $A \cup B$ are either vertices of $A$ or $B$ or intersection points of their sides. and O(n^2) we can find all such points and in O(n^2 log n) have them sorted in say x-axis. Lets call such sorted list as L.

Algo:

1. Calculate L.

2. Do a horizontal sweep, and events in this sweep are members of L. for each point check whether in lies in both $A$ and $B$ if not remove.

3. once done with step 2, take a convex hull of points left in L and return as the convex polygon $A \cup B$.
*/
}

int InBoundingBox(MyLine a, MyPoint p)
{


    if (p.x <min(a.a.x, a.b.x))
        return 0;

    if (p.x > max(a.a.x, a.b.x))
        return 0;

    if (p.y <min(a.a.y, a.b.y))
        return 0;

    if (p.y > max(a.a.y, a.b.y))
        return 0;

    return 1;

}
MyPoint Intersects( MyLine first, MyLine second)
{

	MyPoint intersect;
	intersect.x=intersect.y=0;

	//this line

	double a1 = (first.b.y - first.a.y);

	double b1 = (first.a.x - first.b.x);

	double c1 = (first.b.x*first.a.y - first.a.x*first.b.y);


	//Line to test against
	double a2 = (second.b.y - second.a.y);
	double b2 = (second.a.x - second.b.x);
	double c2 = (second.b.x*second.a.y - second.a.x*second.b.y);

	double denom = a1*b2 - a2*b1;

	//Check for parallel lines
	if(denom == 0) { return intersect; }

	//Get the intersection point
	intersect.x = ( (b1*c2 - b2*c1)/denom);
	intersect.y = ( (a2*c1 - a1*c2)/denom);

	//InBoundingBox tests to see if the point is in the bounding box for
		//a line segment. The point must be in both lines' bounding boxes to
		//register and intersection.
	if( InBoundingBox( first,intersect )==0 || InBoundingBox( second,intersect )==0 )
		{
			intersect.x=0;
			intersect.y = 0;
		}

	return intersect;

}

int IsUnique(MyPoint p)
{
    for(int i=0;i<numberOfPoints;i++)    {
        if (p.x == P[i].x && p.y == P[i].y)
            return 0;
    }

    return 1;
}

 void parse2()
{
	double one,two;
	char ch;

	for(int i=0;i<numberOfPoints;i++)
	{
		ch='0';
		while(ch!=']')
			ii>>ch;

		ii>>one;
		P[i].x=one;
		//ii>>ch;

		ii>>two;
		P[i].y=two;
	}
}

void PolygonIntersection(MyPoint *p1, MyPoint *p2, double *p3x, double *p3y, int n, int m)
{
	int count =0;

	for(int i=0;i<n;i++)
	{
		MyLine l1;

		if(IsInsidePolygon(p2,p1[i],m))
		{
			p3x[count]=p1[i].x;
			p3y[count]=p1[i].y;
			count++;
		}

		l1.a=p1[i];
		if(i<n-1)
			l1.b=p1[i+1];
		else
			l1.b=p1[0];

		for(int j=0;j<m;j++)
		{
			MyLine l2;

			if(IsInsidePolygon(p1,p2[j],n))
			{
				p3x[count]=p2[j].x;
				p3y[count]=p2[j].y;
				count++;
			}


			l2.a=p2[j];
			if(j<m-1)
				l2.b=p2[j+1];
			else
				l2.b=p2[0];

			MyPoint temp = Intersects(l1,l2);
			if(temp.x!=0||temp.y!=0)
			{
				if(IsInsidePolygon(p2,temp,m)&&
					IsInsidePolygon(p1,temp,n)	)
				{
					p3x[count]=temp.x;
					p3y[count]=temp.y;
					count++;
				}
			}

		}

	}

}

extern "C" {
void polygonintersection(double *p1x, double *p1y,
		double *p2x, double *p2y,
		double *p3x, double *p3y,
		int n, int m)
{
	MyPoint *p1,*p2;
	p1=(MyPoint *) malloc(sizeof(MyPoint)*n);
	p2=(MyPoint *) malloc(sizeof(MyPoint)*m);

	for(int i=0;i<n;i++)
	{
		p1[i].x=p1x[i];
		p1[i].y=p1y[i];
	}

	for(int i=0;i<m;i++)
	{
		p2[i].x=p2x[i];
		p2[i].y=p2y[i];
	}
	PolygonIntersection(p1, p2, p3x, p3y,  n, m);
}

} // extern "C"


int main()

{

    numberOfPoints=13;
    ii.open("/home/mudassir/works/depth44.txt");
    parse2();
    P[13].x=10.0;
    P[13].y=10.0;
    cout<<"see :"<<P[35]<<"\n";
    cout<<IsInsidePolygon(P,P[13],12);

	return 0;

}
